home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 8: LINUX Games / Linux Cubed Series 8 - LINUX Games.iso / games / x11 / rpg / crossfir.001 / crossfir~ / eutl / chain-hash / hash_func.c < prev    next >
C/C++ Source or Header  |  1994-09-19  |  5KB  |  189 lines
  1. /* Modified even a little bit more by Eric Anderson */
  2. /* __eutl_default_hash_func defined at end */
  3.  
  4. /*-
  5.  * Copyright (c) 1990, 1993
  6.  *    The Regents of the University of California.  All rights reserved.
  7.  *
  8.  * This code is derived from software contributed to Berkeley by
  9.  * Margo Seltzer.
  10.  *
  11.  * Redistribution and use in source and binary forms, with or without
  12.  * modification, are permitted provided that the following conditions
  13.  * are met:
  14.  * 1. Redistributions of source code must retain the above copyright
  15.  *    notice, this list of conditions and the following disclaimer.
  16.  * 2. Redistributions in binary form must reproduce the above copyright
  17.  *    notice, this list of conditions and the following disclaimer in the
  18.  *    documentation and/or other materials provided with the distribution.
  19.  * 3. All advertising materials mentioning features or use of this software
  20.  *    must display the following acknowledgement:
  21.  *    This product includes software developed by the University of
  22.  *    California, Berkeley and its contributors.
  23.  * 4. Neither the name of the University nor the names of its contributors
  24.  *    may be used to endorse or promote products derived from this software
  25.  *    without specific prior written permission.
  26.  *
  27.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  28.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  29.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  30.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  31.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  32.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  33.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  34.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  35.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  36.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  37.  * SUCH DAMAGE.
  38.  */
  39.  
  40. #if defined(LIBC_SCCS) && !defined(lint)
  41. static char sccsid[] = "@(#)hash_func.c    8.1 (Berkeley) 6/4/93";
  42. #endif /* LIBC_SCCS and not lint */
  43.  
  44. #include <sys/types.h>
  45. #include <chain-hash.h>
  46.  
  47. #if 0
  48. /* Don't bother compiling the others if we can't even get to them */
  49.  
  50. /******************************* HASH FUNCTIONS **************************/
  51. /*
  52.  * Assume that we've already split the bucket to which this key hashes,
  53.  * calculate that bucket, and check that in fact we did already split it.
  54.  *
  55.  * This came from ejb's hsearch.
  56.  */
  57.  
  58. #define PRIME1        37
  59. #define PRIME2        1048583
  60.  
  61. static int
  62. hash1(key, len)
  63.     register u_char *key;
  64.     register int len;
  65. {
  66.     register int h;
  67.  
  68.     h = 0;
  69.     /* Convert string to integer */
  70.     while (len--)
  71.         h = h * PRIME1 ^ (*key++ - ' ');
  72.     h %= PRIME2;
  73.     return (h);
  74. }
  75.  
  76. /*
  77.  * Phong's linear congruential hash
  78.  */
  79. #define dcharhash(h, c)    ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
  80.  
  81. static int
  82. hash2(key, len)
  83.     register u_char *key;
  84.     int len;
  85. {
  86.     register u_char *e, c;
  87.     register int h;
  88.  
  89.     e = key + len;
  90.     for (h = 0; key != e;) {
  91.         c = *key++;
  92.         if (!c && key > e)
  93.             break;
  94.         dcharhash(h, c);
  95.     }
  96.     return (h);
  97. }
  98.  
  99. /*
  100.  * This is INCREDIBLY ugly, but fast.  We break the string up into 8 byte
  101.  * units.  On the first time through the loop we get the "leftover bytes"
  102.  * (strlen % 8).  On every other iteration, we perform 8 HASHC's so we handle
  103.  * all 8 bytes.  Essentially, this saves us 7 cmp & branch instructions.  If
  104.  * this routine is heavily used enough, it's worth the ugly coding.
  105.  *
  106.  * OZ's original sdbm hash
  107.  */
  108. static int
  109. hash3(key, len)
  110.     register u_char *key;
  111.     register int len;
  112. {
  113.     register int n, loop;
  114.  
  115. #define HASHC   n = *key++ + 65599 * n
  116.  
  117.     n = 0;
  118.     if (len > 0) {
  119.         loop = (len + 8 - 1) >> 3;
  120.  
  121.         switch (len & (8 - 1)) {
  122.         case 0:
  123.             do {    /* All fall throughs */
  124.                 HASHC;
  125.         case 7:
  126.                 HASHC;
  127.         case 6:
  128.                 HASHC;
  129.         case 5:
  130.                 HASHC;
  131.         case 4:
  132.                 HASHC;
  133.         case 3:
  134.                 HASHC;
  135.         case 2:
  136.                 HASHC;
  137.         case 1:
  138.                 HASHC;
  139.             } while (--loop);
  140.         }
  141.  
  142.     }
  143.     return (n);
  144. }
  145. #endif
  146.  
  147. /* Hash function from Chris Torek. */
  148. static UM32B
  149. hash4(register unsigned char *key,register xint len)
  150. {
  151.     register xint h, loop;
  152.  
  153. #define HASH4a   h = (h << 5) - h + *key++;
  154. #define HASH4b   h = (h << 5) + h + *key++;
  155. #define HASH4 HASH4b
  156.  
  157.     h = 0;
  158.     if (len > 0) {
  159.         loop = (len + 8 - 1) >> 3;
  160.  
  161.         switch (len & (8 - 1)) {
  162.         case 0:
  163.             do {    /* All fall throughs */
  164.                 HASH4;
  165.         case 7:
  166.                 HASH4;
  167.         case 6:
  168.                 HASH4;
  169.         case 5:
  170.                 HASH4;
  171.         case 4:
  172.                 HASH4;
  173.         case 3:
  174.                 HASH4;
  175.         case 2:
  176.                 HASH4;
  177.         case 1:
  178.                 HASH4;
  179.             } while (--loop);
  180.         }
  181.  
  182.     }
  183.     return (h);
  184. }
  185.  
  186. /* Global default hash function */
  187. HashFunction __eutl_default_hash = hash4;
  188.  
  189.